package com.lxq.LeetCode.searchInsert;

public class Solution {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        System.out.println(searchInsert(nums, 7));
    }

    public static int searchInsert(int[] nums, int target) {
        return bitSearch(nums, 0, nums.length - 1, target);
    }

    public static int bitSearch(int[] nums, int low, int high, int key) {
        if (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == key) {
                return mid;
            } else if (nums[mid] < key) {
                return bitSearch(nums, mid + 1, high, key);
            } else {
                return bitSearch(nums, low, mid - 1, key);
            }
        } else {
            return low;
        }
    }
}
